# -*- coding: utf-8 -*-
"""
作者: liuzaiqiang
邮箱: zaiqiangliu@163.com
地址: 新疆大学
创建时间: 2025/11/21 18:24
功能描述:


定义势能函数Φ=2*size - capacity，平摊成本为 “真实成本 + 势能变化”，最终证明平摊成本为 O (1)。
"""


class DynamicArrayPotential:
    def __init__(self, initial_capacity=1):
        self.data = [None] * initial_capacity
        self.size = 0
        self.capacity = initial_capacity
        self.potential = 0  # 初始势能
        self.actual_costs = []
        self.amortized_costs = []

    def resize(self, new_capacity):
        """扩容操作，返回真实成本"""
        copy_cost = self.size
        new_data = [None] * new_capacity
        for i in range(self.size):
            new_data[i] = self.data[i]
        self.data = new_data
        self.capacity = new_capacity
        return copy_cost

    def append(self):
        """添加元素操作，势能函数Φ=2*size - capacity"""
        # 计算操作前的势能
        prev_potential = 2 * self.size - self.capacity

        # 真实成本：基础操作（1） + 扩容成本（若需）
        base_cost = 1
        actual_cost = base_cost
        if self.size == self.capacity:
            copy_cost = self.resize(2 * self.capacity)
            actual_cost += copy_cost
        self.size += 1
        self.actual_costs.append(actual_cost)

        # 计算操作后的势能
        current_potential = 2 * self.size - self.capacity

        # 平摊成本 = 真实成本 + 势能变化
        amortized_cost = actual_cost + (current_potential - prev_potential)
        self.amortized_costs.append(amortized_cost)

        # 更新势能
        self.potential = current_potential
        assert self.potential >= -1, "势能需非负（初始状态可能为-1，后续会恢复）"

    def potential_analysis(self, n):
        """执行n次append并分析"""
        for _ in range(n):
            self.append()
        total_actual_cost = sum(self.actual_costs)
        total_amortized_cost = sum(self.amortized_costs)
        return {
            "total_actual_cost": total_actual_cost,
            "total_amortized_cost": total_amortized_cost,
            "final_potential": self.potential,
            "amortized_cost_per_op": total_amortized_cost / n
        }


# 示例：执行20次append
array = DynamicArrayPotential(initial_capacity=1)
result = array.potential_analysis(20)
print("\n动态数组势能方法分析结果：")
print(f"总真实成本: {result['total_actual_cost']}")
print(f"总平摊成本: {result['total_amortized_cost']}")
print(f"最终势能: {result['final_potential']}")
print(f"每次操作平摊成本: {result['amortized_cost_per_op']:.2f}（理论上接近3）")